This invention relates to generally to a method and apparatus for transmitting of data on a communications network. More specifically, this invention relates to timely forwarding and delivery of data packets over the network to Voice over Intemet Protocol (VoIP) gateways (see for example: [M. Hamdi, O. Verscheure, J-P Hubaux, I. Dalgic, and P. Wang, Voice Service Interworking and IP Networks, IEEE Communications Magazine, May 1999, pp. 104-111]). Consequently, between anytwo VoIP gateways the end-to-end performance parameters, such as, loss, delay and jitter, have deterministic guarantees.
The proliferation of high-speed communications links, fast processors, and affordable, multimedia-ready personal computers brings about the need for wide area networks that can carry streaming of real-time data packets, from various circuit switched telephony network sources (e.g., analog telephones, ISDN telephones, T1 lines, T3 lines, etc.--see for example: [W. Stallings, ISDN: An Introduction, MacMillan Publishing Company, 1989]). However, the end-to-end transport requirements of real time multimedia applications present a major challenge that cannot be solved satisfactorily by current networking technologies. Such applications as video teleconferencing, and audio and video group (many-to-many) multicasting generate data at a wide range of bit rates and require predictable, stable performance and strict limits on loss rates, end-to-end delay bounds, and delay variations (also known as "jitter"). These characteristics and performance requirements are incompatible with the services that current circuit and packet switching networks can offer.
Circuit-switched networks, which are still the main carrier of streams of real-time traffic, are designed for telephony service and cannot be easily enhanced to support multiple services or carry multimedia traffic. Its synchronous byte switching enables circuitswitching networks to transport data streams at constant rates with little delay or jitter. However, since circuit-switching networks allocate resources exclusively for individual connections, they suffer from low utilization under bursty traffic. Moreover, it is difficult to dynamically allocate circuits of widely different capacities, which makes it a challenge to support multimedia traffic. Finally, the synchronous byte switching of Synchronous Optical NETwork (SONET) or Synchronous Digital Hierarchy (SDH), requires increasingly more precise clock synchronization as the lines speed increases [John C. Bellamy, Digital Network Synchronization, IEEE Communications Magazine, April 1995, pp. 70-83].
Packet switching networks like IP (Internet Protocol)-based Internet and Intranets [see, for example, A. Tannebaum, Computer Networks (3rd Ed) Prentice Hall, 1996] and ATM (Asynchronous Transfer Mode) [see, for example, Handel et al., ATM Networks: Concepts, Protocols, and Applications, (2nd Ed.) Addison-Wesley, 1994] handle bursty data more efficiently than circuit switching, due to their statistical multiplexing of the packet streams. However, current packet switches and routers operate asynchronously and provide "best effort" service only, in which end-to-end delay and jitter are neither guaranteed nor bounded. Furthermore, statistical variations of traffic intensity often lead to congestion that results in excessive delays and loss of packets, thereby significantly reducing the fidelity of real-time streams at their points of reception.
Efforts to define advanced services for both IP and ATM networks have been conducted in two levels: (1) definition of service, and (2) specification of methods for providing different services to different packet stra& The former defines interfaces, data formats, and performance objectives. The latter specifies procedures for processing packets by hosts and switches/routers. The types of services that defined for ATM include constant bit rate (CBR), variable bit rate (VBR) and available bit rate (ABR).
The methods for providing different services under packet switching fall under the general title of Quality of Service (QoS). Prior art in QoS can be divided into two parts: (1) traffic shaping with local timing without deadline scheduling, for example [Demers et al., Analysis and Simulation Of A Fair Queuing Algorithm, ACM Computer Communication Review (SIGCOMM'89), pp. 3-12, 1989; S. J. Golestani, Congestion Free Communication In High-Speed Packet Networks, IEEE Transcripts on Communications, COM-39(12): 1802-1812, December 1991; Parekh et al.,A Generalized Processor Sharing Approach To Flow Control-The Multiple Node Case, IEEM/ACM T. on Networking, 2(2): 137-150, 1994], and (2) traffic shaping with deadline scheduling, for example [Ferrari et al., A Scheme For Real-Time Channel Establishment In Wide Area Networks, IEEE Journal on Selected Areas in Communication, SAC-8(4): 368-379, April 1990]. Both of these approaches rely on manipulation of local queues by each router with little or no coordination with other routers. These approaches have inherent limitations when used to transport real-time streams. When traffic shaping without deadline scheduling is configured to operate at high utilization with no loss, the delay and jitter are inversely proportional to the connection bandwidth, which means that low rate connections may experience large delay and jitter inside the network. In traffic shaping with deadline scheduling the delay and jitter are controlled at the expense of possible congestion and loss.
The real-time transport protocol (RTP) [H. Schultzrinne et. al, RTP: A Transport Protocolfor Real-Time Applications, IBEF Request for Comment RFC1889, January 1996] is a method for encapsulating time-sensitive data packets and attaching to the data time related information like time stamps and packet sequence number. RTP is currently the accepted method for transporting real time streams over IP internetworks and packet audio/video telephony based on lIU-T H.323.
One approach to an optical network that uses synchronization was introduced in the synchronous optical hypergraph [Y. Ofek, The Topology, Algofithms And Analysis Of A Synchronous Optical Hypergraph Architecture, Ph.D. Dissertation, Electrical Engineering Department, University of illinois at Urbana, Report No. UIUCDCS-R-87 1343, May 1987], which also relates to how to integrate packet telephony using synchronization [Y.
Ofek, Integration Of Voice Communication On A Synchronous Optical Hypergraph, INFOCOM'88, 1988]. In the synchronous optical hypergraph, the forwarding is performed over hyper-edges, which are passive optical stars. In [Li et al., Pseudo-Isochronous Cell Switching In ATM Networks, IEEE INFOCOM'94, pp. 428-437, 1994; Li et al., TimeDriven Priority: Flow Control For Real-Time Heterogeneous Internetworkig, IEEE INFOCOM'96, 1996] the synchronous optical hypergraph idea was applied to networks with an arbitrary topology and with point-to point links. The two papers [Li et al., PseudIsochronous Cell Switching InATMNetworks, IEEE JNFOCOM'94, pages 428-437, 1994; Li et al., Time-Driven Priority: Flow Control For Real-Time Heterogeneous Internetworking, IEE INFOCOM'96, 1996] provide an abstract (high level) description of what is called "RISC-like forwarding", in which a packet is forwarded, with little if any details, one hop every time frame in a manner similar to the execution of instructions in a Reduced Instruction Set Computer (RISC) machine.